#include<bits/stdc++.h>
using namespace std;

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};

//*****************************        解法一        ****************************//

// class Solution {
// public:
//     void flatten(TreeNode* root) {
//         vector<TreeNode*> source;
//         if(!root)return;
//         preorder_traversal(root, source);  
//         TreeNode* mov = root;
//         for(int i = 1; i < source.size(); i++){
//             mov->left = nullptr;
//             mov->right = source[i];
//             mov = mov->right;
//         }
//         mov->left = mov->right = nullptr;
//     }

//     //前序遍历
//     void preorder_traversal(TreeNode* root, vector<TreeNode*>& source) {
//         source.emplace_back(root);
//         if(root->left){preorder_traversal(root->left, source);}
//         if(root->right){preorder_traversal(root->right, source);}
//     }
// };
// /**
//  * @brief 2022.2.14 先先序遍历一遍，
//  * 把节点顺序存起来，再下一遍建立链表，时间 O(n)，空间 O(n)。
//  */


//*****************************        解法二        ****************************//

class Solution {
public:
    void flatten(TreeNode* root) {
        TreeNode* mov = root;
        while(mov){
            if(mov->left){
                TreeNode* temp = mov->left;
                while(temp->right)temp = temp->right;
                temp->right = mov->right;
                mov->right = mov->left;
                mov->left = nullptr;
            }
            mov = mov->right;
        }
    }
};
/**
 * @brief 2022.2.14 可以不用额外的数组存遍历顺序，随遍历随建表。
 * 对于当前节点，如果左子节点不为空，那么把当前节点的右子节点作为
 * 左子节点的最右子节点的右子节点，然后把左子节点作为当前节点的
 * 右子节点，将当前节点的左子节点设置为空。
 */